package suanfa.linklist.第一章第一节;

import suanfa.linklist.Node;

public class Test {


    private static Node RecursiveReverse(Node head){

        if(head==null || head.next==null){
            return head;
        }

        Node newHead = RecursiveReverse(head.next);//为什么走完这一行，head就从01234567变成了67？

        //这里为什么用两个next？
        //把当前遍历的节点加到后面节点你序号链表的尾部
        head.next.next=head;//这行代码也很难理解，走完这行代码，head的值就变成永远67，67循环下去了，所以下一行要把他的next置为null

        head.next=null;

        return newHead;

    }

    private static void reverse(Node head){
        if(head==null){
            return;
        }
        Node firstNode = head.next;

        Node newHead = RecursiveReverse(firstNode);

        head.next=newHead;



    }

    private static void reversePrint(Node  firstNode){
        if(firstNode==null){
            return;
        }

        reversePrint(firstNode.next);

        System.out.print(firstNode.data+" ");
    }

    public static void main(String[] args) {
        Node head = new Node();

        head.next=null;

        Node tmp;
        Node cur=head;

        //构造单链表，这个也理解怎么实现的
        for (int i = 0; i < 8; i++) {

            //这个必须放到外面定义，for循环里每次都new一个，链表的next永远是null，不对，放外面也一样
            //Node tmp=new Node();
            tmp=new Node();

            //这两行是为了构建最新的节点，即最后的节点
            tmp.data=i;
            tmp.next=null;

            cur.next=tmp;//这一行很关键，走完这一行，head的值就变了。但为什么cur变了，head也会跟着变？

            cur=tmp;//这里是为了让cur等于最后一个节点的值

        }

        System.out.print("逆序前：");
        for(cur=head.next;cur!=null;cur=cur.next){
            //注意这里不是println
            System.out.print(cur.data+" ");
        }


        System.out.print("逆序后：");

        reverse(head);

        for(cur=head.next;cur!=null;cur=cur.next){
            //注意这里不是println
            System.out.print(cur.data+" ");
        }

//        System.out.println();
//        reversePrint(head);
//        for(cur=head.next;cur!=null;cur=cur.next){
//            //注意这里不是println
//            System.out.print(cur.data+" ");
//        }


    }
}
